1. Field of the Invention
The present invention relates generally to the field of cryptography, and more particularly to an apparatus and method for performing a Montgomery type modular multiplication for use in the encryption/decryption on information and digital signature technology.
2. Description of the Related Art
In communication systems using smart cards and cyber money for electronic commerce, mobile communication devices such as cellular telephones, small-sized computers, etc., it is desirable to transport information (electronic text or data) safely by encrypting/decrypting the information or conducting a digital signature process for the information. Here, the term “digital signature” refers to a technique that “signs” electronic texts with an electronic signature in an electronic exchange of information, similar to that done conventionally on paper. With the rapid increase of the number of Internet users and the frequent transmission of personal information over the Internet, there is a vital need for safe transmission of information through unsecured channels.
Various proposed algorithms such as RSA (Rivest-Shamir-Adleman), ElGamal, Schnorr, etc., have been employed for the encryption/decryption techniques and the digital signature technology using a public key system. The RSA algorithm-based ISO (International Standard Organization)/IEC (International Electrotechnical Commission) 9796 has been adapted as an international standard of these algorithms, DSA (Digital Signature Standard) as a modification of ElGamal has been adapted in the U.S.A., GOSSTANDART (commonly abbreviated as “GOST”) has been adapted in Russia, and KC-DSA has been adapted in Korea. However, various communication systems in current use have adapted many PKCSs (Public Key Cryptography Standards). The above-mentioned algorithms require operation for modular exponentiation, memodN, which incorporates repetitive performance of modular multiplication, A·BmodN.
Many algorithms which perform modular exponentiation and modular multiplication required to generate/verify a digital signature based on a public key cipher such as the RSA have been proposed, for example, R. L. Rivest et al, “A Method For Obtaining Digital Signatures And Public-Key Crytosystems,” Communications of the ACM, Vol. 21, pp. 120-126, 1978; P. L. Montgomery, “Modular Multiplication Without Trial Division,” Math. Of Comp., Vol. 44, No. 170, pp. 519-521, 1985; S. R. Dusse and B. S. Kaliski Jr., “A Cryptographic Library For The Motorola DSP5600,” Proc. Eurocrypto'90, pp. 230-244, 199; and Spronger-Verlag, A. Bosselaers, R. Govaerts and J. Vandewalle, “Comparison Of Three Modular Reduction Functions,” Advances in Cryptology-CRYPTO'93, pp. 175-186, 1993. From the paper by D. R. Stinson, “Cryptography”, CRC Press, 1995, of these algorithms, the Montgomery algorithm has been found to be the most efficient in view of calculation efficiency in modular multiplication for modular exponentiation required for various algorithms, but it is not an efficient algorithm for simple modular multiplication. U.S. Pat. No. 6,185,596 discloses an example of an apparatus implemented by the Montgomery algorithm.
As mentioned above, many algorithms and architectures have been proposed for the public key encryption/decryption and electronic signature. However, since modular multiplication apparatuses according to most of the proposed algorithms and architectures are designed for high-speed public key encryption/decryption, they have a disadvantage in that a great number of gates are required and a large amount of power is consumed. Therefore, they are not suitable for the resource-limited environment like in the smart card.